/**
 * 缺失的第一个正数
 *
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * 示例 1：
 * 输入：nums = [1,2,0]
 * 输出：3
 * 解释：范围 [1,2] 中的数字都在数组中。
 *
 * 示例 2：
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 * 解释：1 在数组中，但 2 没有。
 *
 * 示例 3：
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 * 解释：最小的正数 1 没有出现。
 *
 * 提示：
 * 1 <= nums.length <= 105
 * -231 <= nums[i] <= 231 - 1
 */

/**
 * 这题要求我们用在时间复杂度为 O(n) 解决, 要是没有这一条约定, 我们可以先将数组排序,
 * 后面再用二分查找找到那一个缺失的正数
 * 还要求了空间复杂度为 O(1), 要是没有要求, 我们可以创建一个 Set 来先将所有的数都加进去,
 * 后面在寻找第一个缺失的正数
 *
 * 那有这些限制, 我们可以将这个数组原地排序, 怎么来优化呢, 我们知道缺失的一个数字, 一定在
 * 数组长度包括的范围之内, 要是大于这个范围之内的话也就一定是 n + 1了, 所以我们可以将在这个
 * 范围内的数字放入他们对应下标的数组位置中, 要是之间有一个地方的连续性断了, 那么第一个缺失的
 * 数字就是他, 当然要是第一个断了的位置, 要是一直都没有断, 那么就是 n + 1
 * 这里有两个小细节
 * 1. 当我们要替换的位置就是原来的数字, 这个时候说明了我们遇到两个相同的数了, 且他已经放入了他应当的
 * 位置, 这个时候我们跳过就可以了
 * 2. 要是在我们交换位置的时候这个位置就跳过了, 但是要是我们交换来的数在这个位置也是不对的, 那这个数
 * 就没有考虑到, 所以这个时候我们要将 i--, 让他在看一遍这个数, 不用担心回进入死循环, 因为当这个位置到他
 * 对应的位置时, 会跳过
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {

    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
        test.firstMissingPositive(new int[]{-1,4,2,1,9,10});

    }

    public int firstMissingPositive(int[] nums) {

        // 数组长度, 也就是缺失数字的范围
        int n = nums.length;

        // 第一次循环我们将范围内的数字放入对应的位置
        for (int i = 0; i < n; i++) {

            // 当前数字
            int current = nums[i];

            // 这里条件要在 范围内, 还要求对应的位置没有正确填入该数
            if (current > 0 && current < n && nums[current - 1] != current) {

                // 这里交换两个数
                swap(nums, i, current - 1);

                // 记得这个位置要在判断一遍
                i--;
            }
        }

        // 这里在遍历一遍就是在寻找第一个缺失的数字了
        for (int i = 0; i < n; i++) {

            // 第一个下标不对应的数字就是缺失的第一个数字
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }

        // 要是前面买有缺失就是 n + 1
        return n + 1;
    }

    private void swap (int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}